/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution450 {

    public static void main(String args[]) {
        Solution450 s = new Solution450();
    }

    public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode sRoot = new TreeNode(0);
        sRoot.left = root;
        dfs(sRoot, root, key, true);
        return sRoot.left;
    }

    public void dfs(TreeNode p, TreeNode cur, int key, boolean isLeft) {
        if (cur == null) {
            return;
        }
        if (cur.val == key) {
            delete(p, cur, isLeft);
        } else if (cur.val > key) {
            dfs(cur, cur.left, key, true);
        } else {
            dfs(cur, cur.right, key, false);
        }
    }

    public void delete(TreeNode p, TreeNode cur, boolean isLeft) {
        if (cur.left == null && cur.right != null) {
            if (isLeft) {
                p.left = cur.right;
            } else {
                p.right = cur.right;
            }
        } else if (cur.left != null && cur.right == null) {
            if (isLeft) {
                p.left = cur.left;
            } else {
                p.right = cur.left;
            }
        } else if (cur.left != null && cur.right != null) {
            TreeNode rl = cur.right.left;
            cur.right.left = cur.left;
            if (rl != null) {
                TreeNode lr = cur.left;
                while (lr.right != null) {
                    lr = lr.right;
                }
                lr.right = rl;
            }
            if (isLeft) {
                p.left = cur.right;
            } else {
                p.right = cur.right;
            }
        } else{
            if (isLeft) {
                p.left = null;
            } else {
                p.right = null;
            }
        }
    }
}
